#include <bits/stdc++.h>
using namespace std;

/*
3260. 找出最大的 N 位 K 回文数
已解答
困难
相关标签
相关企业
提示
给你两个 正整数 n 和 k。

如果整数 x 满足以下全部条件，则该整数是一个 k 回文数：

x 是一个 回文数。
x 可以被 k 整除。
以字符串形式返回 最大的  n 位 k 回文数。

注意，该整数 不 含前导零。

 

示例 1：

输入： n = 3, k = 5

输出： "595"

解释：

595 是最大的 3 位 k 回文数。

示例 2：

输入： n = 1, k = 4

输出： "8"

解释：

1 位 k 回文数只有 4 和 8。

示例 3：

输入： n = 5, k = 6

输出： "89898"

 

提示：

1 <= n <= 105
1 <= k <= 9
*/

// 法一
class Solution {
	public:
	/* 
	功能：检查字符串表示的数值是否能被7整除
	参数：s - 由数字字符组成的字符串
	返回值：能被7整除返回true，否则false
	算法：逐位计算余数，避免大数溢出（时间复杂度O(n)）
	[3,8](@ref)
	*/
	bool Check(string s) {
		int r = 0; // 余数累加器
		for (int i=0; i<s.size(); ++i) {
			// 将当前数字并入余数计算
			r = r*10 + (s[i] - '0'); // 当前数值 = 余数*10 + 新数字
			
			// 计算当前余数能减去7的最大倍数
			int j = 0;
			while (7*(j+1) <= r) 
				++j;
			r -= 7*j;     // 更新余数
		}
		return r == 0;
	}

	/*
	功能：生成最大的n位k回文数
	参数：
		n - 回文数的位数
		k - 必须能被k整除
	返回值：满足条件的最大回文数字符串
	算法：根据k值的不同采用构造法生成回文数
	[1,8](@ref)
	*/
	string largestPalindrome(int n, int k) {
		// 初始化最大可能的回文数（全9填充）
		string ans(n, '9');
		
		// 根据k值分类构造最优解
		if (k == 2) {  // 末位必须为偶数，首位取最大偶数8
			ans[0] = ans[n-1] = '8';
		}
		else if (k == 4) {  // 构造双8对称结构提升整除概率
			ans[0] = ans[n-1] = '8';
			if (n > 2)  // 中间位也填充8
				ans[1] = ans[n-2] = '8';
		}
		else if (k == 5) {  // 末尾必须为5或0，取最大5构造
			ans[0] = ans[n-1] = '5';
		}
		else if (k == 6) {  // 特殊构造模式
			if (n == 1) return "6";
			if (n == 2) return "66";
			if (n == 3) return "888";  // 888是最大的3位6回文数
			ans[0] = ans[n-1] = '8';
			// 根据奇偶性处理中间位
			if (n % 2 == 0) 
				ans[n/2] = ans[n/2-1] = '7';  // 中间填充7提升整除概率
			else 
				ans[n/2] = '8';  // 保持对称性
		}
		else if (k == 7) {  // 需要动态验证的复杂情况
			if (n < 3) {  // 小位数直接全7填充
				fill(ans.begin(), ans.end(), '7');
				return ans;
			}
			// 从高位到低位尝试不同数字组合
			for (int i=9; i>=0; --i) {
				// 根据奇偶性设置中间对称位
				if (n%2 == 0) 
					ans[n/2] = ans[n/2-1] = i + '0';
				else
					ans[n/2] = i + '0';
				if (Check(ans))  // 验证是否满足条件
					return ans;
			}
		}
		else if (k == 8) {  // 多位置8的构造模式
			if (n < 6) {  // 小位数全8填充
				fill(ans.begin(), ans.end(), '8');
				return ans;
			}
			// 高位多位置8提升数值大小
			ans[0] = ans[n-1] = '8';
			ans[1] = ans[n-2] = '8';
			ans[2] = ans[n-3] = '8';
		}
		return ans;
	}
};

//法二
class Solution {
	public:
	string largestPalindrome(int n, int K) {
		int P[n + 1];
		P[0] = 1;
		for (int i = 1; i <= n; i++)
			P[i] = P[i - 1] * 10 % K;

		typedef pair<int, int> pii;
		pii f[n][K];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < K; j++)
				f[i][j] = {-1, -1};

		// 初值：先把回文数正中间的位置填上
		int idx;
		if (n & 1) {
			idx = n / 2;
			for (int d = 9; d >= 0; d--) {
				int t = P[n - 1 - idx] * d % K;
				if (f[idx][t].first < 0)
					f[idx][t] = {d, -1};
			}
		} else {
			idx = n / 2 - 1;
			for (int d = 9; d >= 0; d--) {
				int t = (P[n - 1 - idx] + P[idx]) * d % K;
				if (f[idx][t].first < 0)
					f[idx][t] = {d, -1};
			}
		}

		// 套 DP 方程
		for (int i = idx - 1; i >= 0; i--)
			for (int j = 0; j < K; j++) {
				for (int d = 9; d >= 0; d--) {
					int t = (P[n - 1 - i] + P[i]) * d % K;
					t = (j - t + K) % K;
					if (f[i + 1][t].first >= 0) {
						f[i][j] = {d, t};
						break;
					}
				}
			}

		// 从 f(0, 0) 倒过来构造答案
		string ans1, ans2;
		for (int i = 0, j = 0; i <= idx; i++) {
			ans1.push_back(f[i][j].first + '0');
			if (n % 2 == 0 || i < idx)
				ans2.push_back(f[i][j].first + '0');
			j = f[i][j].second;
		}
		reverse(ans2.begin(), ans2.end());
		ans1 += ans2;
		return ans1;
	}
};